The programs evolved use a language similar to LISP. It consists of the following elements:
The list-like structure of the language was chosen to make the genetic crossover operation simple. The programs are represented as trees. During crossover a random node is selected in each parent. Two children are formed by swapping the subtrees below the selected nodes.
The system starts with a population of 500 randomly generated programs. In each generation each program is run and its fitness score is recorded. Here fitness is the number of food squares consumed in 400 operations. Programs are proportionally selected for reproduction based on their fitness. 90% of the time selected pairs of programs are crossed over (sexually reproduced), generating two child programs. 10% of the time selected programs are reproduced unchanged. Over time the more fit individuals become predominant in the population. In this way genetic programming successfully searches the space of all possible programs for ones which satisfy the test criteria. By maintaining a population of 500 individuals the algorithm is performing 500 searches in parallel. This is similar to the randomized parallel search technique used in hill climbing to avoid local maxima. According to Koza, based on Holland's schema theorem [Holland, 1975] genetic programming actually achieves a much greater degree of parallel search. But other authors such as Peter Bentley [Bentley, 1999] question the schema theorem and its applicability to genetic programming, so I will leave it for another presentation...